class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
https://leetcode.cn/problems/permutations-ii/description/

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
        """
        def permute(nums):
            if (len(nums) == 1):
                return [[nums[0]]]
            first = nums[0]
            permutes = permute(nums[1:])

            result = []
            for p in permutes:
                for i in range(0, len(p) + 1):
                    r = list(p)
                    r.insert(i, first)
                    result.append(r)
            return result


        permutes = permute(nums)

        exist = set()
        result = []
        for p in permutes:
            t = tuple(p)
            if t not in exist:
                result.append(p)
                exist.add(t)

        return result
